package main.leetcode.offer.secondround.from03to50;

import main.datastruc.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/** 37.序列化二叉树 */
public class ex37 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        System.out.println(root);
        ex37 test = new ex37();
        String str = test.Serialize(root);
        System.out.println(str);
        //        System.out.println(str = test.Serialize(root));
        System.out.println(test.Deserialize(str));
    }

    String Serialize(TreeNode root) {
        StringBuilder res = new StringBuilder();
        if (root == null) {
            return res.toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (node == null) {
                res.append("null ");
                continue;
            }
            res.append(node.val).append(' ');
            queue.add(node.left);
            queue.add(node.right);
        }
        return res.toString();
    }

    TreeNode Deserialize(String str) {
        String[] values = str.split(" ");
        if (values.length == 0 || values[0].isEmpty()) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.add(root);
        int index = 1;
        TreeNode node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (node == null) {
                continue;
            }
            node.left =
                    "null".equals(values[index])
                            ? null
                            : new TreeNode(Integer.parseInt(values[index]));
            queue.add(node.left);
            ++index;
            node.right =
                    "null".equals(values[index])
                            ? null
                            : new TreeNode(Integer.parseInt(values[index]));
            queue.add(node.right);
            ++index;
        }
        return root;
    }
}
